# -*- coding: utf-8 -*-
"""
Created on Mon Jan 13 21:20:35 2020

@author: Administrator
"""

#《数据结构（第2版）》题目集
# 实例1.1 最大子列和问题
"""
# 方案一：
def test():
    length = int(input())
    data = str(input()).split(' ')
    data = [int(ele) for ele in data]
    
    max_result = data[0]
    for i in range(length):
        for j in range(i,length):
            sub_sum = sum_by_index(data, i, j)
            if  sub_sum > max_result:
                max_result = sub_sum
                
    print(max_result)

def sum_by_index(data, start, end):
    
    length = len(data)
    
    if start < 0 or end > (length-1):
        return
    
    sum_result = 0
    for i in range(start, end+1):
        sum_result += data[i]
    return sum_result

#data = [1,2,3,4,5]
#print(sum_by_index(data, 1, 3))
#test()

# 方案二：
def test2():
    length = int(input())
    data = str(input()).split(' ')
    data = [int(ele) for ele in data]
    
    max_result = data[0]
    for i in range(length):
        sub_sum = 0
        for j in range(i,length):
            sub_sum += data[j]
            if  sub_sum > max_result:
                max_result = sub_sum
                
    print(max_result)
    
#test2()

# 方案三
def test3():
    length = int(input())
    data = str(input()).split(' ')
    data = [int(ele) for ele in data]
    
    max_result = this_result = 0
    for i in range(length):
        this_result += data[i]
        
        if this_result > max_result:
            max_result = this_result
        elif this_result < 0:
            this_result = 0
    print(max_result)
    
#test3()
"""
# 习题2,1 简单计算器
# 模拟简单运算器的工作。假设计算器只能进行加减乘除运算，运算数和结果都是整数，
# 四种运算符的优先级相同，按从左到右的顺序计算。
# 思路：
# 输入："1+2*10-10/2"作为一个字符串，重新组织数据结构
# 分为：numbers：[1, 2, 10, 10, 2] labesl: ['+', '*', '-', '/', '='] 
# 每次取numbers 列表的前两个元素运算。
# 细节：除0、非法字符
"""
def test():
    data = str(input())
    
    number = ''
    numbers = []
    labels = []
    
    for ele in data:

        if ele.isdigit():
            number += ele
        else:
            # 如果有非法运算符
            if not is_valid(ele):
                print("ERROR")
                return         # 如果非法，是跳过继续还是结束？
            numbers.append(int(number))  # 转int
            number = ''
            labels.append(ele)
    
    labels.pop() # 剔除=
    result = 0
    while labels:
        label = labels.pop(0)
        num_a = numbers.pop(0)
        num_b = numbers.pop(0)
        result, flag = calculate(num_a, num_b, label)
        if flag == False:
            return
        numbers.insert(0, result)
    
    print(numbers.pop())

def is_valid(ele):
    if ele == "=" or ele == "+" or ele == "-" or ele == "*" or ele == "/":
        return True
    return False

def calculate(num_a, num_b, label):
    result = 0
    flag = True
    if label == "+":
        result = num_a + num_b
    elif label == "-":
        result = num_a - num_b
    elif label == "*":
        result = num_a * num_b
    elif label == "/":
        if num_b == 0:
            print("ERROR")
            flag = False
        else:
            result = num_a // num_b

    return result, flag
#print(calculate(2,0,"/"))

test()
"""

# 习题2.2 数组循环左移
"""
def test():
    meta = str(input()).split(' ')
    data = str(input()).split(' ')
    move = int(meta[1])
    for i in range(move):
        temp = data.pop(0)
        data.append(temp)
        
    print(' '.join(data))

test()
"""
#习题2.3 数列求和-加强版
# 方案一：求出N位的项A..A，循环累加各项的和
# 测试点：
# A超出整型范围
# N位数为最小，或者A为最小
# N位数为最大，或者A为最大  （超时）
"""
def test():
    meta = str(input()).split(' ')
    base = meta[0]
    length = int(meta[1])
    
    result = 0
    for i in range(1,length+1):
        result += int(base*i)
        
    print(result)
    
test()
"""
#方案二： 直接结算最终结果的各个位的数值
# 个位：(A * N + carry进位) % 10
# 十位：(A * (N - 1) + carry个位的进位) % 10
# ...
# 运行超时
"""
def test():
    meta = str(input()).split(' ')
    base = int(meta[0])
    length = int(meta[1])
    result = []
    carry = 0
    if length == 0:
        print(0)
        return
    for i in range(length,0,-1):
        result.append(str((base * i + carry) % 10))
        carry = (base * i + carry) // 10
    final = reversed(result)
    print(int(''.join(final)))

test()
"""
# 习题2.8 输出全排列
# 请编写程序输出前n个正整数的全排列（n<10），并通过9个测试用例（即n从1到9）观察n逐步增大时程序的运行时间。
""" 时间复杂度太高
import random as rnd
def test():
    number = ''
    used = []
    length = int(input())
    for i in range(length):
        digit, used = get_unique_digit(length - i, used)
        number += str(digit)
    
    print(number)

def get_unique_digit(index, used):
    while True:
        digit = rnd.randint(1,index)
        if digit not in used:
            used.append(digit)
            return digit, used
        
test()
"""

# 2.8输出全排列
# 输出1到n的全排列。排列的输出顺序为字典序
# 思路：使用回溯思想（深度优先遍历）
# 什么时候进行下一次迭代？
# 什么时候返回迭代？
# 什么时候回溯？即回溯点在哪里？

# 答：用一次迭代的确定一位数字，即当前位数确定好后，确定下一位时，进行下一次迭代
# 最终，当找到一个解得时候（即所有位数确定的时候），迭代返回
# 当前点（数字）不可用时，按字典序到下一个。
# 穷尽到最后一位后，无法再找到新解，使用回溯的方式，变换上一位的数字，以求找到新解
"""
def test():
    visited = []
    number = []
    
    length = int(input())
    
    for i in range(length+1):
        visited.append(0)
        
    dfs(1, length, number, visited)
    
def dfs(step, length, number, visited):
    if step == length+1:
#        print(number)
        number = [str(ele) for ele in number]
        print(''.join(number))
    else:
        for i in range(1,length+1):
            if visited[i] == 0:
                number.append(i)
                visited[i] = 1
                dfs(step+1, length, number, visited)
                visited[i] = 0
                number.pop()
test()
"""
#习题3.4 最长连续递增子序列 
#给定一个顺序存储的线性表n，请设计一个算法查找该线性表中最长的连续递增子序列。
# 按照循环的顺序逐个判断，如果比之前的大，继续下一个；如果比之前的小，重新开始
# 注意只需要找到最大的一组递增序列即可。

# 测试用例：
# 1.全顺序
# 2.全逆序
# 3.最小n
# 4.随机最大n
"""
def test():
    
    length = int(input())
    raw = str(input()).split(' ')
    data = [int(ele) for ele in raw]
    
    max_result = data[0]
    count = 1
    temp = [data[0]]
    result = {'length':1, 'list':[data[0]]}
    max_count = 1
    
    
    for i in range(1,length):
        # 如果序列递增
        if data[i] > max_result:
            max_result = data[i]
            temp.append(data[i])
            count += 1
        else: # 如果序列不增或则减小，更新初始值
            max_result = data[i]
            count = 1
            temp = [data[i]]
            
        if count > max_count:
            max_count = count
            result['length'] = count
            result['list'] = temp
    # 打印最大序列
    final = [str(ele) for ele in result['list']]
    print(' '.join(final))
    
test()
"""